from typing import Optional, List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        p = dummy
        p1 = list1
        p2 = list2
        while p1 and p2:
            if p1.val < p2.val:
                p.next = p1
                p1 = p1.next
            else:
                p.next = p2
                p2 = p2.next
            p = p.next

        if p1:
            p.next = p1

        if p2:
            p.next = p2

        return dummy.next

    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        dummy1 = ListNode(-1)
        dummy2 = ListNode(-1)
        p1 = dummy1
        p2 = dummy2
        p = head

        while p:
            if p.val < x:
                p1.next = p
                p1 = p1.next
            else:
                p2.next = p
                p2 = p2.next

            temp = p.next
            p.next = None
            p = temp

        p1.next = dummy2.next
        return dummy1.next
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0:
            return None
        nums = []
        for item in lists:
            while item:
                nums.append(item.val)
                item = item.next

        nums.sort()
        dummy = ListNode(-1)
        cur = dummy
        for item in nums:
            cur.next = ListNode(item)
            cur = cur.next

        return dummy.next

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(-1)
        dummy.next = head
        prevNth = dummy
        cur = head
        for i in range(n):
            cur = cur.next

        while cur:
            prevNth = prevNth.next
            cur = cur.next

        prevNth.next = prevNth.next.next

        return dummy.next

    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        if not fast:
            return slow
        return slow

    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                break

        if not fast or not fast.next:
            return None

        slow = head
        while slow != fast:
            fast = fast.next
            slow = slow.next

        return slow

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p1, p2 = headA, headB
        while p1 != p2:
            if p1:
                p1 = p1.next
            else:
                p1 = headB

            if p2:
                p2 = p2.next
            else:
                p2 = headA

        return p1

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None or head.next == None:
            return head

        last = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return last

    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == 1:
            return self.reverseN(head, right)
        head.next = self.reverseBetween(head.next, left - 1, right - 1)
        return head

    def reverseN(self, head, n):
        if n == 1:
            self.successor = head.next
            return head
        last = self.reverseN(head.next, n - 1)
        head.next.next = head
        head.next = self.successor
        return last

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head == None:
            return head
        start, end = head, head
        for i in range(k):
            if end == None:
                return head
            end = end.next

        newStart = self.reverseBetweenK(start, end)
        start.next = self.reverseKGroup(end, k)
        return newStart

    def reverseBetweenK(self, start, end):
        prev, cur, next = None, start, None
        while cur != end:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        return prev

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        self.left = head
        return self.traverseLinkedList(head)

    def traverseLinkedList(self, right):
        if right == None:
            return True
        res = self.traverseLinkedList(right.next)
        res = res & (True if self.left.val == right.val else False)
        self.left = self.left.next
        return res

    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None:
            return head
        slow, fast = head, head.next
        while fast != None:
            if slow.val == fast.val:
                slow.next = fast.next
            else:
                slow = slow.next
            fast = fast.next
        return head

    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k == 0 or head is None or head.next is None:
            return head
        n, iter = 1, head
        while iter.next is not None:
            iter = iter.next
            n += 1
        rest = n - k % n
        if rest == n:
            return head
        iter.next = head
        while rest > 0:
            rest -= 1
            iter = iter.next
        res = iter.next
        iter.next = None
        return res


